\section{图}
\subsection{图的相关定义}
\begin{definition}[图的定义]
	G=(V,E),V是顶点vertex集合，E是边edge的集合。
\end{definition}
\begin{definition}[完全图：]顶点之间两两有边。
\end{definition}
\begin{definition}[稀疏图：]边的条数小于完全图的5\%。
\end{definition}
\begin{itemize}
	\item 无向图：1-2和2-1相同。
	\item 有向图：边之间是有向的.如下：$v_1->v_4$有边，$v_4-v_1$不直接关联。
\end{itemize}
\begin{figure}[!htbp]
	\centering
	\includegraphics[width=0.5\textwidth]{dag}
	\label{fig:dag}
	\caption{无向图}
\end{figure}
带权图如\figref{fig:graph_with_weight}：
\begin{figure}[H]
	\centering
	\includegraphics[width=0.5\textwidth]{graph_with_weight}
	\caption{带权图}
	\label{fig:graph_with_weight}
\end{figure}

\begin{definition}[入度]
	入度：指向节点的边数。
\end{definition}
\begin{definition}[入度]
	出度：指出节点的边。
\end{definition}
\begin{definition}[子图：]
	图$G(V,E),G'(V',E')$中，如果$V'\leq V,E'\leq E$并且$E'$中的边所关联的顶点都在$V'$中，则称$G'$是$G$的子图。
\end{definition}
从顶点$V_p$到顶点$V_q$的路径，顶点序列$V_p,V_{i1},V_{i2},\ldots,V_{in},V_{q}$使得$(V_p,V_{i1}),(V_{i1},v_{i2}),\ldots ,(V_{in},V_q)$（若对有向图，则使得$<V_p,V_{i1}>,<V_{i1},V_{i2}>,\ldots,<V_{in},V_q>$）都在E中。
如果路径可以表示为$v_1v_2,v_3,\ldots,v_{n-1},v_n$，如果$v_1=v_n$，且没有重复的边，那么此路径称为\textbf{环}。\textcolor{red}{无向图路径长度大于等于3}。
\begin{definition}[有根图]
	一个有向图中，若存在一个顶点$V_0$，从此顶点有路径可以到达途中其它所有顶点，则称此有向图为有根的图，$V_0$是图的根。
\end{definition}
\begin{definition}[连通性]
	对于无向图$G(V,E)$而言，如果从$V_1$到$V_2$有一条路经（从$V_2$到$V_1$也一定有一条路经），则称$V_1$和$V_2$是连通的。
\end{definition}
\begin{definition}[强连通]
	有向图$G(V,E)$如果两个顶点$v_i,v_j$间有一条$v_i$到$v_j$的有向路径，同时还有一条$v_j$到$v_i$的有向路径，则称两个顶点强连通。
\end{definition}
\begin{definition}[强连通分量]
	非强连通图有向图的极大强连通子图，称为强连通分量。
\end{definition}
图的抽象数据类型：
\begin{longlisting}
	\caption{图的抽象数据结构}
	\cppfile[firstline=1,lastline=14]{samples/graph/graph_template.cc}
	\label{code:graph_ast}
\end{longlisting}

\begin{definition}[邻接矩阵]
	表示顶点之间的邻接关系，即有没有边。设$G=<V,E>$是一个n个顶点的图，则图的邻接矩阵是一个二位数组A[i,j],定义如下：
	\begin{equation*}
		A[i,j]=
		\begin{cases}
			1,\quad \text{若}(V_i,V_j)\in E\text{或者}<V_i,V_j>\in E \\
			0,\quad \text{若}(V_i,V_j)\notin E\text{或者}<V_i,V_j>\notin E
		\end{cases}
	\end{equation*}
\end{definition}
对于n个顶点的图，邻接矩阵的空间代价都为$(n^2)$和边数无关。
\begin{figure}[!htbp]
	\centering
	\includegraphics[width=0.5\textwidth]{adj-matrix}
	\caption{有向图的邻接矩阵}
	\label{fig:adj_matrix}
\end{figure}
\figref{fig:adj_matrix}的邻接矩阵\ref{eq:adj_matrix}：
\begin{equation}
	\centering
	A = \begin{bmatrix}
		0                  & \textcolor{red}{1} & 0 & 0                  & 0                  \\
		\textcolor{red}{1} & 0                  & 0 & 0                  & \textcolor{red}{1} \\
		0                  & \textcolor{red}{1} & 0 & \textcolor{red}{1} & 0                  \\
		\textcolor{red}{1} & 0                  & 0 & 0                  & 0                  \\
		0                  & 0                  & 0 & \textcolor{red}{1} & 0                  \\
	\end{bmatrix}
	\label{eq:adj_matrix}
\end{equation}
\begin{figure}[!htbp]
	\centering
	\includegraphics[width=0.5\textwidth]{adj-no-direct}
	\label{fig:adj-no-direct}
	\caption{无向图}
\end{figure}

\begin{equation*}
	\centering
	A = \begin{bmatrix}
		0                   & \textcolor{red}{3} & 0                  & \textcolor{red}{15} \\
		\textcolor{red}{3}  & 0                  & \textcolor{red}{4} & 0                   \\
		0                   & \textcolor{red}{4} & 0                  & \textcolor{red}{6}  \\
		\textcolor{red}{15} & 0                  & \textcolor{red}{6} & 0
	\end{bmatrix}
	\label{eq:adj-no-direct}
\end{equation*}
邻接矩阵的类定义：
\begin{longlisting}
	\caption{邻接矩阵AST}
	\cppfile[firstline=1,lastline=21]{samples/graph/adj_matrix_template.cc}
	\label{code:adj_matrix_ast}
\end{longlisting}

\begin{definition}[稀疏因子]
	在$m\times n$的矩阵中，有t个非零元素，则稀疏因子$\delta$为：\[\delta = \frac{t}{m\times n}\]如果$\delta$小于0.05,则可认为是稀疏矩阵。
\end{definition}
对于稀疏图,可以采用邻接表存储法：
\begin{itemize}
	\item 边较少,邻接矩阵就会出现大量的零元素。
	\item 邻接矩阵的零元素将耗费大量的存储空间和时间。
\end{itemize}
\textbf{邻接表}(adjacency list) 链式存储结构:
\begin{itemize}
	\item  顶点表目有两个域:顶点数据域和指向此顶点边表指针域。
	\item  边表把依附于同一个顶点 $v_i$的边(即邻接矩阵中同一行,的非0元素)组织成一个单链表。由两个主要的域组成:
	      \begin{itemize}
		      \item  与顶点 $v_i$ 邻接的另一顶点的序号。
		      \item  指向边表中下一个边表目的指针。
	      \end{itemize}
\end{itemize}
\begin{figure}[!htbp]
	\centering
	\includegraphics[width=\textwidth]{adj_node}
	\caption{链式邻接表的顶点和边}
	\label{adj_node}
\end{figure}
\emph{无向图同一条边在邻接表中出现两次}

\begin{figure}[H]
	\centering
	\includegraphics[width=\textwidth]{adj_table}
	\caption{无向图的邻接表}
	\label{fig:adj_table}
\end{figure}
\begin{figure}[H]
	\centering
	\includegraphics[width=\textwidth]{adj_node_weight_ast}
	\label{fig:adj_node_weight_ast}
	\caption{带权图邻接表表示}
\end{figure}
表头数据结构定义如下：
\begin{cpp}
class VNode {
	public:
	int data;
	ArcNode* firstarc;
	VNode(int d,ArcNode* fp);
	VNode(int d);
};
\end{cpp}
表中节点结构：
\begin{cpp}
class ArcNode {
	public:
	int adjvex;
	ArchNode *nextarc;
	int info;
	ArcNode(int adj, int i, ArchNode *ap);
	ArcNode(int adj, int i);
};
\end{cpp}

\begin{figure}[H]
	\centering
	\includegraphics[width=\textwidth]{graph_adj_table}
	\caption{出入度分别表示}
\end{figure}
图邻接表的空间代价：
\begin{itemize}
	\item n 个顶点e条边的无向图,需用 (n + 2e) 个存储单元，n 个顶点 e 条边的有向图需用 (n + e) 个存储单元。
	\item 当边数e 很小时,邻接表可以节省大量的存储空间，边表中表目顺序往往按照顶点编号从小到大排列。
\end{itemize}
\textbf{十字链表 (Orthogonal List)} 可以看成是邻接表和逆邻接表的结合，对应于有向图的每一条弧有一个表目,共有5个域:头 headvex、尾 tailvex 、下一条共尾弧 tailnextarc;下一条共头弧 headnextarc;弧权值等 info 域。顶点表目由3个域组成:data 域;firstinarc 第一条以该顶点为终点的弧;firstoutarc 第一条以该顶点为始点的弧。稀疏矩阵的十字链表由行和列的指针序列。每个结点都包含两个指针:同一行的后继,同一列的后继。
\begin{figure}[!htbp]
	\centering
	\includegraphics[width=0.5\textwidth]{dg11}
	\caption{稀疏矩阵的十字链表}
\end{figure}
\subsection{图的遍历}
\begin{definition}[图的遍历]
	给出一个图G和其中任意一个顶点$V_0$,从$V_0$出发系统地访问G中所有的顶点,每个顶点访问而且只访问一次
\end{definition}
从一个顶点出发,试探性访问其余顶点,同时必须考虑到下列情况：
\begin{itemize}
	\item 从一顶点出发,可能不能到达所有其它的顶点。如：非连通图。
	\item 也有可能会陷入死循环。如：存在回路的图。
\end{itemize}
解决的办法是：为每个顶点保留一个 \textbf{标志位 (mark bit)}，算法开始时,所有顶点的标志位置零。 在遍历的过程中,当某个顶点被访问时,其标志位就被标记为已访问。图遍历的算法框架：
\begin{longlisting}
	\caption{图遍历算法模板}
	\cppfile[firstline=1,lastline=8]{samples/graph/travel_template.cc}
	\label{code:traverse}
\end{longlisting}
\textbf{深度优先遍历DFS}：类似于树的先根次序遍历,尽可能先对纵深方向进行搜索。
\begin{itemize}
	\item 选取一个未访问的点$v_0$作为源点。
	\item 访问顶点$v_0$。
	\item 递归地深搜遍历$v_0$邻接到的其它顶点。
	\item 重复上述过程直至从 $v_0$ 有路径可达的顶点都已被访问过。
	\item 再选取其它未访问顶点作为源点做深搜,直到图的所有顶点都被访问过。
\end{itemize}
\begin{figure}[!htbp]
	\centering
	\includegraphics[width=0.5\textwidth]{graph_dfs}
	\caption{深度优先搜索示意}
	\label{fig:graph_dfs}
\end{figure}
搜索顺序为:$a\rightarrow b\rightarrow c\rightarrow f\rightarrow d\rightarrow e\rightarrow g$，\figref{fig:graph_dfs}深度优先遍历DFS。
\begin{longlisting}
	\caption{DFS 队列实现模板}
	\cppfile[firstline=1,lastline=9]{samples/graph/dfs_sample.cc}
	\label{code:DFS-template}
\end{longlisting}

\textbf{广度优先遍历（BFS}）：其遍历过程是从图中的某一个顶点$v_0$出发，访问并标记顶点$v_0$之后一层层横向搜索$v_0$的所有邻接点，对这些临界点一层层横向搜索，直到$v_0$有路径可达的顶点都已经被访问过。在选取其它没有访问的顶点作为远点广搜，直到所有点都被访问过。
\begin{longlisting}
	\caption{BFS 队列实现模板}
	\cppfile[firstline=1,lastline=18]{samples/graph/bfs_sample.cc}
	\label{code:BFS-template}
\end{longlisting}

图搜索的时间复杂度：DFS 和 BFS 每个顶点访问一次,对每一条边处理一次 (无向图的每条边从两个方向处理)采用邻接表表示时,有向图总代价为$\Theta(n+e)$,无向图为$\Theta(n+2e)$。采用邻接矩阵表示时,处理所有的边需要 $\Theta(n^2)$的时间 ,所以总代价为$\Theta(n+n^2)=\Theta(n^2)$
\subsection{拓扑排序 (topological sort)}\label{chap:toposort}
\textbf{拓扑排序}：对于 有向无环图 $G= (V,E) ,V $里顶点的线性序列称作一个 \textcolor{red}{拓扑序列},该顶点序列满足:
\begin{itemize}
	\item 若在有向无环图 $G$ 中从顶点 $v_i$ 到$v_j$有一条路径,则在序列中顶点 $v_i$ 必在顶点 $v_j$ 之前
\end{itemize}
\textbf{拓扑排序}：将一个 \textcolor{red}{有向无环图}中所有顶点在不违反先决条件关系的前提下排成线性序列的过程称为\textcolor{red}{拓扑排序}

\begin{table}[!htbp]
	\centering
	\caption{大学课程信息}
	\begin{tabular}{ccc}
		\toprule
		课程代号  & 课程名称  & 先修课程      \\
		\midrule
		$C_1$ & 高等数学  &           \\
		$C_2$ & 程序设计  &           \\
		$C_3$ & 离散数学  & $C_1,C_2$ \\
		$C_4$ & 数据结构  & $C_2,C_3$ \\
		$C_5$ & 算法分析  & $C_2$     \\
		$C_6$ & 编译技术  & $C_4,C_5$ \\
		$C_7$ & 操作系统  & $C_4,C_9$ \\
		$C_8$ & 普通物理  & $C_1$     \\
		$C_9$ & 计算机原理 & $C_8$     \\
		\bottomrule
	\end{tabular}
\end{table}
\begin{figure}[!htbp]
	\centering
	\includegraphics[width=0.5\textwidth]{topocourse}
	\caption{大学课程DAG}
\end{figure}
\textcolor{red}{拓扑排序的方法}：
任何有向无环图 (DAG) ,其顶点都可以排在一个拓扑序列里,其拓扑排序的方法是:
\begin{enumerate}
	\item 从图中选择任意一个入度为0的顶点且输出之。
	\item 从图中删掉此顶点及其所有的出边,将其入度减少1。
	\item 回到第 (1) 步继续执行。
\end{enumerate}
\textcolor{red}{队列实现的图拓扑排序}：
\begin{longlisting}
	\caption{拓扑排序队列实现}
	\cppfile[firstline=1,lastline=25]{samples/graph/topo_sort_template.cc}
	\label{code:toposort_queue}
\end{longlisting}

\begin{figure}[!htbp]
	\centering
	\includesvg[width=0.5\textwidth]{toposort_course}
	\label{fig:topsort_course}
	\caption{大学课程拓扑排序的拓扑序列}
\end{figure}
\textcolor{red}{深度优先搜索实现的拓扑排序}
\begin{longlisting}
	\caption{深搜实现拓扑排序}
	\cppfile[firstline=27,lastline=38]{samples/graph/topo_sort_template.cc}
	\label{code:top_sort_template}
\end{longlisting}

\textcolor{red}{拓扑排序的递归函数}：
\begin{longlisting}
	\caption{拓扑排序的递归函数}
	\cppfile[firstline=40,lastline=47]{samples/graph/topo_sort_template.cc}
	\label{code:toposort_rec}
\end{longlisting}

\textbf{拓扑排序的时间复杂度：}
与图的深度优先搜索方式遍历相同：图的每条边处理一次，图的每个顶点访问一次。采用邻接表表示时,为$\Theta(n+e)$，采用邻接矩阵表示时,为$\Theta(n^2)$。是否支持:有向图、无向图，有回路的图，非连通图，权值为负。
\section{并查集(Union-Find)}
并查集是专门针对连通性的算法。其并、查分别对应着合并不同的集合、查询元素是否在集合中。如下\figref{fig:NodeSets}：
\begin{figure}[!htbp]
	\centering
	\includesvg[width=.5\textwidth]{unionfind}
	\caption{并查集}
	\label{fig:NodeSets}
\end{figure}
图中有三个集合，1、2、0、4属于一个集合、6、3、7属于一个集合、5属于一个集合。为了表示这个集合我们可以使用数组[1,-7,1,6,2,-1,1,3]表示，set数组中存放的值有正数和负数。其中只有代表元素存放负数，这里的"-1"代表索引（节点）5是对应集合的代表元素，"-1"的绝对值也就是"1"说明在代表元素为5的这个集合中，含有元素的个数为1。同理，"-7"代表1是对应集合的代表元素，"-7"的绝对值也就是"7"说明在代表元素为1的这个集合中，含有元素的个数为7。而非代表元素存放正数，相应的值表示该元素的前一个元素（父节点或是索引）。这里的数组含义可以有不同的定义，例如我们可以定义数组索引的值就是索引的父节点，这里说的连通满足如下特征：
\begin{enumerate}
	\item 自反性：节点p和p是连通的。
	\item 对称性：节点p和q是连通的，则节点q和p是连通的。
	\item 传递性：如果节点p和q连通、节点q和r连通，则p和r是连通的。
\end{enumerate}
连通分量：图中没有连通的节点个数。\figref{fig:common_node}如果两个节点连通则他们一定拥有相同的根节点：
\begin{figure}[!htbp]
	\begin{center}
		\includegraphics[width=.5\textwidth]{common_node}
	\end{center}
	\caption{合并节点b和e}
	\label{fig:common_node}
\end{figure}
上图合并过程发现有两种不同的合并方法。这时我们需要定义一个更加合适合并规则：将小一些的数加到大树中。我们可以通过节点的子节点数表征树的大小。如果我们想通过任意节点以O(1)找到其根节点，我们可以将数压缩为一个根节点其他节点都是子节点。根据上面描述，我们实现并查集结构，其主要实现函数Union用来合并集合。isConnected判断是否在同一个集合里。find用来查找节点的父节点。
算法如下：
\begin{cpp}
// 如果没有找到x的根节点
while(parent[x]!=x){
  // 将x的爷爷节点赋值给父节点
  parent[x] = parent[parent[x]];
  // 当前节点上升
  parent[x] = x;
}
\end{cpp}
示意\figref{fig:path_extract}：
\begin{figure}[!htbp]
	\begin{center}
		\includegraphics[width=\textwidth]{path_extract}
	\end{center}
	\caption{路径压缩示意图}
	\label{fig:path_extract}
\end{figure}

\begin{longlisting}
	\caption{并查集实现}
	\cppfile{third_party/coding/cxx/algorithm/datastruct/src/UnionFind.cc}
	\label{code:union_find}
\end{longlisting}
\begin{enumerate}
	\item 因为每个数字节点都和自己连通，所以我们初始化每个数字的父节点为自己。
	\item find(i)用来查找节点i的父节点。如
\end{enumerate}
\subsection{最短路径}
\begin{definition}[单源最短路径(single-source shortest paths)]给定带权图 $G = <V,E>$,其中每条边 $(v_i ,v_j )$ 上的权$W[v_i ,v_j ] $是一个 非负实数 。计算从任给的一个源点 s   到所有其他各结点的最短路径。
\end{definition}
\begin{figure}[!htbp]
	\centering
	\includegraphics[width=0.5\textwidth]{graph_sssp}
	\label{fig:graph_sssp}
	\caption{带权图的最短路径}
\end{figure}
\subsubsection{Prim算法}
加权连通图的最小生成树算法：
\begin{enumerate}
	\item 输入：一个加权连通图，其中顶点集合为V，边集合为E。
	\item 初始化点集合$V_s$中的元素为图中任意节点 x，此时边节点集合$E_s$为空。
	\item 重复下列操作，直到$V_s = V$：
	      \begin{enumerate}
		      \item 在集合E中选取权值最小的边<u, v>，其中u为集合$V_s$中的元素，而v不在$V_s$集合当中，并且v$\in$V（如果存在有多条满足前述条件即具有相同权值的边，则可任意选取其中之一）。
		      \item 将v加入集合$V_s$中，将<u, v>边加入集合$E_s$中。
	      \end{enumerate}
	\item 输出：使用集合$V_s$和$E_s$来描述所得到的最小生成树。
\end{enumerate}
\begin{figure}[!htbp]
	\centering
	\includegraphics[width=0.6\textwidth]{PrimGraph}
	\caption{示意图}
	\label{fig:PrimGraph}
\end{figure}
以\figref{fig:PrimGraph}为例说明Prim算法。
\begin{figure}[!htbp]
	\centering
	\includesvg[width=\textwidth]{prim_example}
	\caption{Prim算法示意图}
	\label{fig:prim_example}
\end{figure}

\begin{enumerate}
	\item 初始化，随机选择一个节点，这里选择节点D。点集合$V_s$包含D。
	\item 于是：
	      \begin{enumerate}
		      \item $V_s\neq V$在集合E中选择权值最小的边<D,A>加入$E_s$，将A加入集合$V_s$。
		      \item $V_s\neq V$在集合E中选择权值最小的边<D,F>加入$E_s$，将F加入集合$V_s$。
		      \item $V_s\neq V$在集合E中选择权值最小的边<A,B>加入$E_s$，将B加入集合$V_s$。
		      \item $V_s\neq V$在集合E中选择权值最小的边<B,E>加入$E_s$，将E加入集合$V_s$。
		      \item $V_s\neq V$在集合E中选择权值最小的边<C,E>加入$E_s$，将C加入集合$V_s$。
		      \item $V_s\neq V$在集合E中选择权值最小的边<E,G>加入$E_s$，将G加入集合$V_s$。
	      \end{enumerate}
	\item 输出：当前$V_s$和$E_s$分别包含的节点和边就是最小生成树的结果。
\end{enumerate}
\subsubsection{Kruskal算法}
Kruskal算法和Prim算法类似，Kruskal算法在图中存在相同权值的边时也有效。对于一个图G=(V,E)，图中包含n个节点算法如下：
\begin{enumerate}
	\item 初始化一个空集合A。并创建n棵树，每棵树只有一个节点。
	\item 按照边的权重从小到大的顺序依次取出每条边检查：
	      \begin{enumerate}
		      \item 如果边上的两个节点属于同一棵树则不能加入森林（会形成环路）。
		      \item 两个节点不属于同一棵树则这条边加入集合A、合并两棵树的节点。
	      \end{enumerate}
	\item 重复上面操作，直到所有的节点都被加入。
\end{enumerate}
\figref{fig:kruskal_graph}
\begin{figure}[!htbp]
	\centering
	\includegraphics[width=.5\textwidth]{kruskal_graph}
	\caption{最小生成树图}
	\label{fig:kruskal_graph}
\end{figure}
算法流程如：
\begin{figure}[!htbp]
	\centering
	\includesvg[width=0.6\textwidth]{kruskal_alg}
	\caption{Kruskal算法示意图}
	\label{fig:longestPath}
\end{figure}
\subsection{单源最短路径}
\begin{lemma}
	给定带权重的有向图$G=(V,E)$和权重函数w，$E\rightarrow \mathbf{R}$。设$p=(v_0,v_1,\cdots,v_k)$为从节点$v_0$到$v_k$的一条最短路径。对任意$i$，$j$。$0\leq i\leq j\leq k$，设$p_{ij}=(v_i,v_{i+1},\cdots,v_{j})$为路径$p$中从$v_i$到$v_j$的一条子路径。那么$p_{ij}$是从节点$v_i$到节点$v_j$的一条最短路径。(最短路径的子路径也是最短路径)
\end{lemma}
\subsubsection{Dijkstra算法}
\textbf{Dijkstra算法的基本思想：}把所有结点分成两组，初始化节点v到其它节点的距离为$\infty$，v的邻接节点$prev[v]$为空。将所有节点加入集合Q。然后初始化节点source的dist[source]距离为0。
\begin{algorithmic}
	\STATE dist[source]$\leftarrow$ 0
	\STATE 创建一个优先队列Q
	\FOR{v in Graph.Vertices}
	\IF{v$\neq$ source}
	\STATE $dist[v]\leftarrow \infty$
	\STATE $prev[v]\leftarrow UNDEFINED$
	\ENDIF
	\STATE $Q.add\_with\_priority(v,dist[v])$
	\ENDFOR
	\WHILE{Q is not empty}
	\STATE u $\leftarrow$ Q.min()
	\FOR{neighbor v of u}
	\STATE alt$\leftarrow$ dist[u]+Graph.Edges(u,v)
	\IF{alt < dist[v]}
	\STATE dist[v]$\leftarrow$ alt
	\STATE prev[b]$\leftarrow$ u
	\STATE Q.decrease(v,alt)
	\ENDIF
	\ENDFOR
	\ENDWHILE
	\RETURN dist[],prev[]

\end{algorithmic}
\begin{figure}[!htbp]
	\centering
	\includegraphics[width=0.5\textwidth]{dijkstra_demo}
	\caption{带权图}
	\label{fig:Dijkstra_process}
\end{figure}
Dijkstra算法例子：
\begin{figure}[!htbp]
	\centering
	\includegraphics[width=\textwidth]{dijkstra_sample}
	\caption{dijkstra算法示意}
\end{figure}
\begin{longlisting}
	\caption{dijkstra算法}
	\cppfile[firstline=1,lastline=36]{samples/graph/dijkstra_template.cc}
	\label{code:dijkstra}
\end{longlisting}
流程：
\begin{enumerate}
	\item 节点0作为起点，当前$dist={0,\infty,\infty,\infty,\infty,\infty,\infty}$，其余节点全部加入Q。
	\item 此时节点Q不为空，则将0的邻接节点1、2取出，距离节点0更近的是节点1，则1移出Q。
	\item 此时距离dist[1]=2。
	\item Q不为空，此时和1、0邻接的节点3、2。最小权重为6。2加入节点。
	\item 此时和1、2节点最接近的节点分别是3和4，到达通过1到达3值为7，通过2到达3结果为14，通过2到达4结果为16，选中节点3，此时最短路径和为7，3移出Q。
	\item 此时3、2邻接节点5、4。通过3到达4最小和为17通过2到达4结果为16，4移出Q。
	\item 和4、3邻接的节点5、6，到达6路径和最小为22，6移出Q。
	\item 和3、4、6邻接的节点为5、到5最短为28，5移出Q、
	\item Q为空，返回。
\end{enumerate}
Dijkstra算法时间代价分析：每次改变D[i].length，不删除,添加一个新值(更小的),作为堆中新元素。旧值被找到时,该结点一定被标记为VISITED,从而被忽略。在最差情况下,它将使堆中元素数目由
$\Theta(|V|)$增加到$\Theta(|E|)$,总的时间代价$\Theta((|V|+|E|)log|E|)$。\textcolor{red}{Dijkstra算法不支持负权值}。即使不存在负的回路,也可能有在后面出现的负权值,从而导致整体计算错误。主要原因是 Dijkstra 算法是贪心法,当作最小取进来后,不会返回去重新计算。

\subsubsection{Bellman-Ford算法}
Bellman-Ford 算法是一种用于计算带权有向图中单源最短路径的算法。该算法由 Richard Bellman 和 Lester Ford 分别发表于 1958 年和 1956 年，而实际上 Edward F. Moore 也在 1957 年发布了相同的算法，因此，此算法也常被称为 Bellman-Ford-Moore 算法。Bellman-Ford 算法和 Dijkstra 算法同为解决单源最短路径的算法。对于带权有向图 G = (V, E)，Dijkstra 算法要求图 G 中边的权值均为非负，而 Bellman-Ford 算法能适应一般的情况（即存在负权边的情况）。一个实现的很好的 Dijkstra 算法比 Bellman-Ford 算法的运行时间要低。

Bellman-Ford 算法采用动态规划（Dynamic Programming）进行设计，实现的时间复杂度为 $O(V\times E)$，其中 V 为顶点数量，E 为边的数量。Dijkstra 算法采用贪心算法（Greedy Algorithm）范式进行设计，普通实现的时间复杂度为 $O(V^2)$，若基于 Fibonacci heap 的最小优先队列实现版本则时间复杂度为 $O(E + VlogV)$。
Bellman-Ford 算法描述：
\begin{enumerate}
	\item 创建源顶点 v 到图中所有顶点的距离的集合 distSet，为图中的所有顶点指定一个距离值，初始均为 Infinite，源顶点距离为 0；
	\item 计算最短路径，执行 V - 1 次遍历；
	\item 对于图中的每条边：如果起点 u 的距离 d 加上边的权值 w 小于终点 v 的距离 d，则更新终点 v 的距离值 d；
	\item 检测图中是否有负权边形成了环，遍历图中的所有边，计算 u 至 v 的距离，如果对于 v 存在更小的距离，则说明存在环；
\end{enumerate}
由于第 k 次迭代时已求得矩阵 $adj^{(k-1)}$ ,那么从结点 $v_i$ 到 $v_j$ 中间结点的序号不大于 k 的最短路径有两种情况:
\begin{itemize}
	\item 一种是中间不经过结点 $v_k$ ,那么此时就有$adj^{(k)} [i,j] = adj^{(k-1)} [i,j]$
	\item 另中间经过结点 v k ,此时 $adj^{(k)} [i,j] < adj^{(k-1)} [i,j]$,
	      那么这条由结点 $v_i$ 经过 $v_k$ 到结点 $v_j$ 的中间结点序号不大于k的最短路径由两段组成$adj^{(k)} [i,j] = adj^{(k-1)} [i,k] + adj^{(k-1)} [k,j]$
\end{itemize}
\begin{figure}[!htbp]
	\centering
	\includegraphics[width=0.5\textwidth]{dg19}
	\caption{Floyd算法示意图}
\end{figure}
代码：
\begin{longlisting}
	\caption{floyd算法}
	\cppfile[firstline=1,lastline=32]{samples/graph/floyd_template.cc}
	\label{code:floyd}
\end{longlisting}
Floyd算法的时间复杂度$\Theta(n^3)$
\subsection{最小生成树实现}
% 实现边和节点类。边的头文件：
% \cppfile{code/offer/ex8/Edge.hpp}
边实现：
% \cppfile{code/offer/ex8/Edge.cc}
节点类定义：
% \cppfile{code/offer/ex8/Node.hpp}
节点类实现：
% \cppfile{code/offer/ex8/Node.cc}
图的头文件：
% \cppfile{code/offer/ex8/CMap.hpp}
图的类实现：
% \cppfile{code/offer/ex8/CMap.cc}
测试函数：
% \cppfile{code/offer/ex8/main.cpp}
\subsection{实现图的深度优先和广度优先算法}
\begin{example}[无向图的DFS和BFS]
	\begin{figure}[!htbp]
		\centering
		\includesvg[width=0.2\textwidth]{no_direct_graph}
		\caption{无向图示意图}
	\end{figure}
	实现DFS遍历（A-B-C-E-F-D-G-H）和 BFS(A-B-D-C-F-G-H-E)
\end{example}
节点的类定义：
% \cppfile{code/offer/dfs/Node.hpp}
节点的实现：
% \cppfile{code/offer/dfs/Node.cc}
图的头文件：
% \cppfile{code/offer/dfs/Graph.hpp}
图的实现：
% \cppfile{code/offer/dfs/Graph.cc}
测试代码:
% \cppfile{code/offer/dfs/main.cpp}
\subsection{二分图}
\begin{definition}[完全二分图]
	设G=(V,E)是一个无向图，如果定点V可以分割为两个互补相交的子集(A,B)，并且图中的每条边(i,j)所关联的两个定点i和j分别属于这个不同的定点集合，则称G是一个二分图。二分图的等价定义：不含有含奇数条边的环（贿赂的长度均为偶数）的图。
\end{definition}
\begin{definition}[匹配]
	匹配是一个边的集合，其中任意两条边都没有公共顶点。
\end{definition}
\begin{figure}[!htbp]
	\centering
	\includegraphics[width=0.5\textwidth]{div_graph}
	\caption{匹配示意图}
	\label{fig:div_graph}
\end{figure}
\figref{fig:div_graph}中图2，1,4,5,7是匹配点，其它顶点为未匹配点,1-5,4-7为匹配边，其它边为非匹配边。
\begin{definition}[最大匹配]
	图中变数最多的匹配称为最大匹配。
\end{definition}
\begin{definition}[完美匹配]
	如果一个图的某个匹配中，所有的顶点都是匹配点，那么他就是一个完美匹配。完美匹配一定是最大匹配（完美匹配的任何一个点都已经匹配，添加一条新的匹配边会和已经有的匹配边冲突）。但并非每个图都存在完美匹配。
\end{definition}
\begin{definition}[交替路]
	从一个未匹配点出发，经过非匹配边，匹配边，非匹配边形成的路径称为交替路。
\end{definition}
\begin{definition}[增广路]
	从一个未匹配点出发，走交替路，如果途径另一个未匹配点（出发的点不算），这条路经称为增广路。
\end{definition}
\begin{figure}[!htbp]
	\centering
	\includegraphics[width=0.5\textwidth]{augument_path}
	\caption{交替路和增广路}
\end{figure}
增广路有一个重要特点：非匹配边比匹配边多一条。因此，研究增广路的意义是改进匹配。只要把增广路中的匹配边和非匹配边的身份交换即可。由于中间的匹配节点不存在其他相连的匹配边，所以这样做不会破坏匹配的性质。交换后，图中的匹配边数目比原来多了 1 条。
\begin{figure}[!htbp]
	\centering
	\includegraphics[width=0.5\textwidth]{argument_path_ex}
	\caption{增广路径例子}
\end{figure}
\begin{remark}[增广路的性质]
	\begin{enumerate}
		\item 有奇数条边。
		\item 起点在二分图的左半边，终点在右半边。
		\item 路径上的点一定是一个在左半边，一个在右半边，交替出现。（其实二分图的性质就决定了这一点，因为二分图同一边的点之间没有边相连，不要忘记哦。）
		\item 整条路径上没有重复的点。
		\item 起点和终点都是目前还没有配对的点，而其它所有点都是已经配好对的。（如图1、图2所示，［1，5］和［2，6］在图1中是两对已经配好对的点；而起点3和终点4目前还没有与其它点配对。）
		\item 路径上的所有第奇数条边都不在原匹配中，所有第偶数条边都出现在原匹配中。（如图1、图2所示，原有的匹配是［1，5］和［2，6］，这两条配匹的边在图2给出的增广路径中分边是第2和第4条边。而增广路径的第1、3、5条边都没有出现在图1给出的匹配中。）
		\item 最后，也是最重要的一条，把增广路径上的所有第奇数条边加入到原匹配中去，并把增广路径中的所有第偶数条边从原匹配中删除（这个操作称为增广路径的取反），则新的匹配数就比原匹配数增加了1个。（如图2所示，新的匹配就是所有蓝色的边，而所有红色的边则从原匹配中删除。则新的匹配数为3。
	\end{enumerate}
\end{remark}
\begin{definition}[最小覆盖]
	最小顶点覆盖是指最少的顶点数使得二分图G中的每条边都至少与其中一个点相关联，二分图的最小顶点覆盖数=二分图的最大匹配数；
	最小路径覆盖也称为最小边覆盖，是指用尽量少的不相交简单路径覆盖二分图中的所有顶点。二分图的最小路径覆盖数=|V|-二分图的最大匹配数；
\end{definition}
\begin{theorem}
	如果从一个点A出发，没有找到增广路径，那么无论再从别的点出发找到多少增广路径来改变现在的匹配，从A出发都永远找不到增广路径。
\end{theorem}
匈牙利算法过程示意图：
\begin{figure}[!htbp]
	\centering
	\includegraphics[width=0.5\textwidth]{hungarian}
	\caption{匈牙利算法示意图（BFS）}
\end{figure}
\begin{figure}[!htbp]
	\centering
	\includegraphics[width=0.5\textwidth]{匈牙利算法}
	\caption{匈牙利算法}
\end{figure}
图2选中x1的第一个连接点(红线)，图3选中x2的第一个连接点y2,图3,x3选中y1发现x3的第一条x3-y1边被占据了，找出x3出发的交错路径。剩余的边x3-y1,x1-y4加到匹配中去。
% \cppfile{code/offer/ex19/test.cc}
\subsection{二分图染色问题}
\begin{example}[二分图染色问题]
	对一个节点（白色），和它相邻的节点（黑色（不同颜色）），所有边两边的节点颜色不同则为二分图，否则不是。
	\begin{figure}[!htbp]
		\centering
		\includegraphics[width=0.5\textwidth]{isdiv}
		\caption{染色例子}
	\end{figure}
\end{example}
% \cppfile{code/arith/ex11/main.cpp}
整个代码以一个起点开头深搜，如果visited是初始化状态，设置他的状态，然后判断相邻节点状态和它是否相同，如果相同，则无法二分，否则，相邻节点被反色。以相邻节点为起点开始搜索，知道结束。
在代码中是否访问visited使用的是int，而不是bool数组。因为visited应该有三种状态，初始状态，设置状态，设置状态的相反状态。
\subsection{环的检测}
\textbf{无向图的环检测方法}
\begin{itemize}
	\item 拓扑排序：找入度为0的顶点，输出顶点，删除边。循环知道无顶点输出。如果输出所有的顶点，则拓扑排序，无环。否则不能拓扑排序，有环。
	\item DFS+回溯：回溯遍历，如果遇到之前访问过的节点，则图中有环。
	\item DFS+判断后退边：在遍历顶点的每一条边时，判断一下这个边的顶点是不是在栈中，如果在栈中说明之前已经访问过，这里再次访问，说明有环存在。
\end{itemize}
